부산대학교자료구조
Scientific Inference Lab

From Links to Hierarchies

Binary Trees

이진트리(binary tree)는 각 노드가 최대 두 자식 노드를 가지는 트리이며, 두 자식 노드는 왼쪽과 오른쪽 자리로 구분된다. 빈 트리이거나, 루트와 왼쪽 부분 트리, 오른쪽 부분 트리로 이루어진다는 재귀 정의로 높이도 부분 트리의 결과를 합쳐 계산한다.

왼쪽과 오른쪽자식 노드가 하나뿐이어도 왼쪽인지 오른쪽인지가 트리를 구분한다.
재귀 정의이진트리는 빈 트리이거나, 루트와 왼쪽·오른쪽 부분 트리로 이루어진다.
height(u)빈 트리는 −1, 그 밖에는 1 + max(height(u.left), height(u.right))다.

자식 노드의 왼쪽·오른쪽 자리를 바꾸면 다른 이진트리가 된다

루트 A 아래의 배치를 바꾸면 왼쪽 자리와 오른쪽 자리에 오는 노드가 바뀐다. 노드 수가 같아도 자리가 다르면 기준 트리와 다른 이진트리다.

왼쪽과 오른쪽 자리기준 이진트리와 고른 배치의 이진트리
왼쪽은 기준 트리, 오른쪽은 고른 배치다. 점선 칸은 비어 있는 자리(빈 부분 트리)다. 빨간 테두리 노드는 기준 트리와 다른 자리에 있는 노드다.

높이는 두 부분 트리의 높이에서 1을 더해 계산한다

노드를 고르면 그 노드를 루트로 삼는 부분 트리와 왼쪽·오른쪽 부분 트리의 높이, 그 둘로 계산한 높이가 바뀐다. 빈 부분 트리의 높이는 −1로 둔다.

부분 트리의 높이노드마다 계산한 높이와 빈 부분 트리
노드 위 파란 수는 그 노드의 높이, 점선 칸의 −1은 빈 부분 트리의 높이다. 초록으로 채운 원이 고른 노드, 옅은 초록 원이 그 부분 트리의 나머지 노드다.

노드 수가 같아도 모양에 따라 높이가 달라진다

노드 수 n과 모양을 바꾸면 트리의 높이가 바뀐다. 한 줄로 이으면 높이가 가장 크고, 위층부터 두 자리씩 채우면 가장 작다.

같은 노드 수의 두 모양노드 수와 모양에 따른 이진트리의 높이
원 하나가 노드다. 왼쪽 숫자는 층의 깊이이며, 가장 깊은 층의 깊이가 트리의 높이다.